package _18_剑指OfferII;

// 数组规模中，找都是否能装满元素，最小数目，可以使用动态规划解决
public class _101_剑指OfferII分割等和子集 {

    public static void main(String[] args) {
        _101_剑指OfferII分割等和子集 v = new _101_剑指OfferII分割等和子集();

        int[] ins = {2, 2, 1, 1};
        System.out.println(v.canPartition(ins));

    }

    // 空间优化
    public boolean canPartition(int[] nums) {
        int total = 0;
        int len = nums.length;
        for (int num : nums) {
            total += num;
        }
        if ((total & 1) == 1) return false;
        total >>= 1;
        boolean[] dp = new boolean[total + 1];
        dp[0] = true;
        for (int i = 1; i <= len; ++i) {
            for (int j = total; j >= nums[i - 1]; --j) {
                dp[j] |= dp[j - nums[i - 1]];
            }
        }

        return dp[total];
    }

    public boolean canPartition1(int[] nums) {
        int total = 0;
        int len = nums.length;
        for (int num : nums) {
            total += num;
        }
        if ((total & 1) == 1) return false;
        total >>= 1;
        boolean[][] dp = new boolean[len + 1][total + 1];
        dp[0][0] = true;
        for (int i = 1; i <= len; ++i) {
            for (int j = 1; j <= total; ++j) {
                if (nums[i - 1] > j) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = dp[i - 1][j - nums[i - 1]] | dp[i - 1][j];
                }
            }
        }

        return dp[len][total];
    }

}
